package com.zyf;

import java.util.Scanner;

/**
 * 7 合并两个有序数组

给定两个有序整数数组,nums1 和nums2 ,将nums2合并到nums1中,使得nums1成为一个有序数组

说明 : 初始化 nums1 和 nums2 的元素数量分别为 m 和 n
           你可以假设nums1有足够的空间(空间大小大于或等于 m+n),来保存nums2中的元素

示例 : 
输入 :  nums1 = {1,2,3,0,0,0} m = 3;
nums2 = {2,5,6}  n=3
输出 : {1,2,2,3,5,6}

 * @author lenovo
 * @Date 2020年7月2日
 * @Time 下午3:39:38
 */
public class _07_mergeArrays {

	public static void main(String[] args) {
		@SuppressWarnings("resource")
		Scanner sc = new Scanner(System.in);
		System.out.println("输入第一个数组长度 : " );
		int m = sc.nextInt();
		int[] arr1 = new int[6];
		System.out.println("输入一个长度为 " + m +"的数组 : " );
		for (int i = 0; i < m; i++) {
			arr1[i] = sc.nextInt();
		}
		System.out.println("输入第二个数组长度 : " );
		int n = sc.nextInt();
		int[] arr2 = new int[n];
		System.out.println("输入一个长度为 " + n +"的数组 : " );
		for (int i = 0; i < arr2.length; i++) {
			arr2[i] = sc.nextInt();
		}
		mergeArrays(arr1 , m , arr2 , n);
		System.out.println("合并后数组为 : " );
		for (int i = 0; i < arr1.length; i++) {
			System.out.print(" "+arr1[i]);
		}
	}
	/**
	 * 合并两个有序数组方法实现
	 * @param arr1
	 * @param m
	 * @param arr2
	 * @param n
	 * 
	 * 思路:
	 * 方法接收两个数组 , 和他们的长度 
	 * 用一个变量 n3 来记录两个数组长度 , 用尾插法往 arr1[] 中插入元素
	 * 假设 arr1[] 的空间足够大 (大于 arr1[] + arr2[]),用 n3 来做下标
	 * n1 和 n2 大于 0 说明 arr1[] 和 arr2[] 中有元素
	 * 循环插入
	 * 循环结束说明其中一个数组插入完成
	 * 
	 * 两种情况:
	 * 	1  arr2[] 数组中的元素插入完成 , 不用管 arr1[] , 因为 arr1[] 的元素就在本数组中
	 * 	2  arr1[] 数组中的元素插入完成 , 在用一个循环插入 arr2[] 中的元素
	 * 
	 */
	public static void mergeArrays(int[] arr1, int m, int[] arr2, int n) {
		int n1 = m-1 ;//n1=2
		int n2 = n-1 ;//n2=2
		int n3 = n+m-1;//计算两个数组的长度,开辟出适当的数组空间
		//arr1  n=3
		//arr2  m=3
		while(n1 >= 0 && n2 >= 0) {
			if (arr1[n1] >= arr2[n2]) {
				arr1[n3--] = arr1[n1--];
			}else {
				arr1[n3--] = arr2[n2--];
			}
		}
		//如果 arr2[] 的存储完了,不用管 arr1[] ,本来就在 arr1[]中
		//把 arr2[] 中剩下的存储到 arr1
		while (n2 >= 0) {
			arr1[n3--] = arr2[n2--];
		}
	}

}
